A database is generally made up of one or several tables of data. The tables are made up of records (also called tuples). A record may comprise several different information elements. A record relating to a credit card customer may, for instance, comprise information regarding the customer's name, his/her current credit, the year he/she became a customer, and information regarding the type of the customer's credit card. The records are often provided with a unique key value. The record relating to the credit card customer may, for instance, be provided with a key that is a customer ID in the form of a number that is unique for the customer.
In order to allow quick and efficient access for database management programs to selected records in a table, one or several indexes are commonly used. The function of an index for a database corresponds to the function of an index in a book. The index provides a list from which a location of a desired element can be derived relatively quickly without having to search through the whole database. Indexes can be of several different types.
U.S. Pat. No. 5,960,194 describes a method for generating a multi-tiered indexing structure for a partitioned database.
A secondary index is an index that associates values of a particular information element with the keys of the records that contain each value in an appropriate field in the table. A secondary index for the example table of credit card customers may, for instance, list the different available types of credit cards and with each type of credit card associate the customer IDs of the customers that have that type of credit card.
An algorithm for optimal selection of secondary indexes is discussed in the article “Optimal Selection of Secondary Indexes” by E. Barcucci et al. Published in IEEE Transactions in Software Engineering, Vol. 16, No. 1, January 1990 pp. 32–38. The algorithm aims at minimizing the cost of transactions in which secondary indexes are involved.
U.S. Pat. No. 5,933,820 describes a method that allows for non-disruptive reorganization of data by using dual pointing with direct and indirect pointing to logically related data and data that is a target of secondary indexes.
When data in a table changes, a secondary index associated with the data may also have to be updated. The secondary index may also be useful to find records that, for instance, are to be updated in the table. Thus there are transactions that start from the table and continue to the secondary index and transactions that start from the secondary index and continue to the table. The transactions may comprise one or several table operations and/or index operations.
A normal write transaction will first operate on the record in the table by means of a write operation and thereafter on the secondary index by means of index update operations, where appropriate. The secondary index will be updated by means of Add Index Entry or Delete Index Entry or both. Add Index Entry is, as the name indicates, an operation wherein a key is added to an index record and Delete Index Entry an operation wherein a key is deleted from an index record.
Read Index Entry and Write Index Entry are operations that start by reading the secondary index and then continue to operate on the table. Read Index Entry involves reading first the keys of a certain index record and then the records of the table that correspond to the read keys. Write Index Entry involves reading the keys of a certain index record and then performing write operations on the records of the table that correspond to the read keys, followed by an update of the secondary index where appropriate.
A locking strategy is used in order to ensure that no conflicting operations are performed simultaneously on the same record or index record, which otherwise could cause errors in the database and the index. The level of concurrency depends on the locking strategy that is used. In a pessimistic locking strategy, concurrency is only allowed between two read operations, while there is no concurrency between two write operations or between a read operation and a write operation. In an environment where secondary indexes are used, which are stored in separate index tables or other types of storage containers, the pessimistic locking strategy gives bad concurrency and, at the same time, causes frequent deadlocks. A deadlock can occur when two different operations have acquired locks that stop the other operation from completing. The deadlock can be resolved by aborting one of the operations. Many of the operations described above give rise to a series of operations that require locks both on records in the table and on index records in the secondary index in order to complete. Since, in addition, some transactions start from the table and others from the secondary index, it is easily understood that a traditional locking strategy, such as the pessimistic locking strategy, often causes deadlocks. Deadlocks are naturally highly undesirable and there is thus a demand for a locking strategy that to a high degree prevents deadlocks from occurring.
U.S. Pat. No. 5,280,612 describes a database system that aims to increase the concurrency in the system and thereby reduce the waiting time for transactions that require locks due to locks set by other transactions. The concurrency is increased by maintaining at least to database versions and allowing operations to be carried out simultaneously on the different versions. The system must for this purpose include means for selection of proper record versions.